import static java.util.Collections.swap;

public class QuickSort1 {
    //快速排序法  挖坑法
    void QuickSort1(int[] arr, int begin, int end)
    {
        if (begin >= end)
            return;
        int left = begin,right = end;
        int key = arr[begin];
        while (begin < end)
        {
            //找小
            while (arr[end] >= key && begin < end)
            {
                --end;
            }
            //小的放到左边的坑里
            arr[begin] = arr[end];
            //找大
            while (arr[begin] <= key && begin < end)
            {
                ++begin;
            }
            //大的放到右边的坑里
            arr[end] = arr[begin];
        }
        arr[begin] = key;
        int keyi = begin;
        //[left,keyi-1]keyi[keyi+1,right]
        QuickSort1(arr, left, keyi - 1);
        QuickSort1(arr, keyi + 1, right);
    }

    //快速排序   hoare版本(左右指针法)
    void QuickSort(int[] arr, int begin, int end)
    {
        //只有一个数或区间不存在
        if (begin >= end)
            return;
        int left = begin;
        int right = end;
        //选左边为key
        int keyi = begin;
        while (begin < end)
        {
            //右边选小   等号防止和key值相等    防止顺序begin和end越界
            while (arr[end] >= arr[keyi] && begin < end)
            {
                --end;
            }
            //左边选大
            while (arr[begin] <= arr[keyi] && begin < end)
            {
                ++begin;
            }
            //小的换到右边，大的换到左边
            //swap(&arr[begin], &arr[end]);
        }
        //swap(&arr[keyi], &arr[end]);
        keyi = end;
        //[left,keyi-1]keyi[keyi+1,right]
        QuickSort(arr, left, keyi - 1);
        QuickSort(arr,keyi + 1,right);
    }


}
